//
// Created by Administrator on 2022/1/26.
//

#ifndef CPP_LEARNING_LEETCODE131_H
#define CPP_LEARNING_LEETCODE131_H
#include <vector>
using namespace std;
#include <math.h>
#include <iostream>
class Solution131 {
public:
    void partitionCaseToString(string& s, vector<vector<string>>& result, vector<int>& partitionCase){
        vector<string> temp;
        //[l, r)
        int l = 0;
        int r = 0;
        for(int i=0; i<partitionCase.size(); i++){
            r += partitionCase[i];
            temp.push_back(string(s, l, partitionCase[i]));
            l = r;
        }

        result.push_back(temp);
    }
    // [l,r]
    bool isPalindromicString(string& s, int l, int r){
        while (l < r){
            if(s[l] != s[r]){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
    void partition(string& s, vector<int>& partitionCase, int& partitionSum, vector<vector<string>>& result){
        if(partitionSum > s.size()) return;

        if(partitionSum == s.size()){
            partitionCaseToString(s,result, partitionCase);
        }

        for(int i=1; i<= s.size() - partitionSum;i++){
            if(isPalindromicString(s, partitionSum, partitionSum + i -1)){
                partitionSum += i;
                partitionCase.push_back(i);
                partition(s, partitionCase, partitionSum, result);
                partitionSum -= i;
                partitionCase.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        //

        // 记录的是每一段的长度
        vector<int> partitionCase;
        int partitionSum = 0;
        vector<vector<string>> result;
        partition(s, partitionCase, partitionSum, result);
        return result;
    }
};

void test131(){
    Solution131 s;
    s.partition( "aabbcac");

}

#endif //CPP_LEARNING_LEETCODE977_H
